package leetcode.sword;

import java.util.Deque;
import java.util.LinkedList;

public class Solution31 {

    public static void main(String[] args) {
        int[] pushed = {1,0};
        int[] popped = {1,0};
        System.out.println(new Solution31().validateStackSequences2(pushed,popped));
//        System.out.println(null==1);
    }

    public boolean validateStackSequences2(int[] pushed, int[] popped) {
        LinkedList<Integer> stack = new LinkedList<>();
        int popIdx = 0, n = popped.length;
        for(int num : pushed){
            stack.addLast(num);
            while(popIdx<n&&popped[popIdx]==stack.peekLast()){
                stack.removeLast();
                popIdx++;
            }
        }
        return stack.isEmpty();
    }

    public boolean validateStackSequences(int[] pushed, int[] popped) {
        int i = 0, j = 0;
        for (int e : pushed) {
            pushed[i] = e;
            while (i >= 0 && pushed[i] == popped[j]) {
                j++;
                i--;
            }
            i++;
        }
        return i == 0;
    }

    public boolean validateStackSequences1(int[] pushed, int[] popped){
        /**
         * 模拟出入栈，如果遇到无法执行的操作说明有问题
         */
        Deque<Integer> stack = new LinkedList<>();
        int i = 0, j = 0, n = pushed.length;
        while (j<n){
            //不满足出栈条件就一直入栈
            while (i<n&&(stack.isEmpty()||stack.peekLast()!=popped[j])){
                stack.offerLast(pushed[i++]);
            }
            if(i>=n&&stack.peekLast()!=popped[j]) return false;
            while (j<n&&!stack.isEmpty()&&stack.peekLast()==popped[j]){
                stack.removeLast();
                j++;
            }
        }
        return true;
    }
}
